<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    /**
     * 输入: word1 = "sea", word2 = "eat"
     * 输出: 2
     * 解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
    */

    // 题目让我们计算将两个字符串变得相同的最少删除次数，那我们可以思考一下，最后这两个字符串会被删成什么样子？
    // 删除的结果不就是它俩的最长公共子序列嘛！
    // 那么，要计算删除的次数，就可以通过最长公共子序列的长度推导出来：

    var minDistance = function (word1, word2) {
      let m = word1.length, n = word2.length;

      let lcs = LCS(word1, word2)
      // "a" "a" => 0
      return (m - lcs) + (n - lcs)

      function LCS(word1, word2) {
        let m = word1.length, n = word2.length;
        let dp = new Array(m + 1).fill('.').map(item => new Array(n + 1).fill(0))

        for (let i = 1; i <= m; i++) {
          for (let j = 1; j <= n; j++) {
            if (word1[i - 1] === word2[j - 1]) {
              dp[i][j] = 1 + dp[i - 1][j - 1]
            } else {
              dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
            }
          }
        }
        return dp[m][n]
      }

    };    
  </script>
</body>

</html>